package greedy_algorithm;

import java.util.Arrays;

public class JumpingGame {

    int[] memo;
    // 主函数
    public int jump(int[] nums) {
        int n = nums.length;
        // 备忘录都初始化为n,相当于INT_MAX
        // 因为从0跳转到 n - 1最多 n - 1步
        memo = new int[n];
        Arrays.fill(memo, n);

        return dp(nums, 0);
    }

    // 定义：从索引p跳到最后一格，至少需要dp(nums,p)步
    private int dp(int[] nums, int p) {
        int n = nums.length;
        // base case
        if (p >= n - 1)
            return 0;
        // 子问题已经计算过
        if (memo[p] != n)
            return memo[p];
        int step = nums[p];
        // 你可以选择跳1步、2步....
        for (int i = 1; i <= step; i++) {
            // 穷举每一个选择
            // 计算每一个子问题的结果
            int subProblem = dp(nums, i);
            // 取其中的最小值作为结果
            memo[p] = Math.min(memo[p], subProblem + 1);
        }
        return memo[p];
    }
}
